package com.sicheng.lc.杂题;

import com.sicheng.algorithm.node.ListNode;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/16 22:27
 */
public class 回文链表 {
    //https://leetcode.cn/problems/palindrome-linked-list/
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null)
            return true;
        ListNode t = new ListNode(-1);
        t.next = head;
        ListNode f = t, s = t;
        while (f != null && f.next != null) {
            f = f.next.next;
            s = s.next;
        }

        // 找到反转链表的头结点
        ListNode h = s.next;
        f = h.next;
        h.next = null;
        while (f != null) {
            s = f.next;
            f.next = h;
            h = f;
            f = s;
        }

        while (head != null && h != null) {
            if (head.val != h.val) {
                return false;
            }
            head = head.next;
            h = h.next;
        }

        return true;

    }
}
